package org.xqh.study.leetcode.algorithm.twopointer;

/**
 * @ClassName LongestOnes
 * @Description https://leetcode-cn.com/problems/max-consecutive-ones-iii/
 * 最大连续1的个数 III
 * @Author xuqianghui
 * @Date 2021/2/19 21:31
 * @Version 1.0
 */
public class LongestOnes {

    public static void main(String[] args) {
        int[] A = {0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
//        System.out.println(longestOnes(A, 3));
        System.out.println(majorityElement(A));
    }


    public static int longestOnes(int[] A, int K) {
        int left = 0, right = 0;
        int maxLen = 0;
        int replace = 0;

        while (right < A.length){
            if(A[right] == 0){
                replace ++;
            }

            if(replace <= K){
                maxLen = Math.max(maxLen, right - left + 1);
            }
            right ++;
            while (replace > K){
                if(A[left] == 0){
                    replace --;
                }
                left ++;
            }
        }
        return maxLen;
    }

    /**
     * 出现次数 大于 n/2 的数字, n 为数组长度
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        return splitCalc(nums, 0, nums.length - 1);
    }

    /**
     * 分治
     * @param nums
     * @param left 左指针
     * @param right 右指针
     * @return
     */
    public static int splitCalc(int[] nums, int left, int right){

        if(left == right){//只有一个元素的情况  众数就是本身
            return nums[left];
        }

        int mid = (right - left)/2 + left;

        int lc = splitCalc(nums, left, mid);
        int rc = splitCalc(nums, mid + 1, right);
        if(lc == rc){
            return lc;
        }

        int leftCount = calcCount(nums, left, mid, lc);
        int rightCount = calcCount(nums, mid + 1, right, rc);

        return leftCount > rightCount ? lc : rc;


    }

    public static int calcCount(int[] nums, int le, int right, int val){
        int count = 0;
        for(int i = le; i <= right; i ++){
            if(nums[i] == val){
                count ++;
            }
        }
        return count;
    }

    /**
     * 投票算法
     * @param nums
     * @return
     */
    public static int voteCalc(int[] nums){
        int candidate = 0;//候选对象
        int count = 0;//计数
        for(int i = 0; i < nums.length; i++){
            if(count == 0){
                candidate = nums[i];
            }
            count += (candidate == nums[i]) ? 1 : -1;
        }
        return candidate;
    }
}
